package linkedlist;
//给一个链表,和一个值x,将链表中大于x的放在前半部分,小于x的放在后半部分
//创建傀儡节点,来简化后续操作
//public class LinkedListProblem2 {
//    public ListNode portion(ListNode phead,int x){
//        if(phead == null){
//            return null;
//        }
//        if(phead.next == null){
//            return phead;
//        }
//        ListNode smallHead = new ListNode(0);
//        ListNode smallTail = smallHead;
//        ListNode largeHead = new ListNode(0);
//        ListNode largeTail = largeHead;
//        for(ListNode cur = phead;phead != null;phead = phead.next){
//            if(cur.val > x){
//                smallTail.next = cur;
//                smallTail = cur;
//            }else{
//                largeTail.next = cur;
//                largeTail = cur;
//            }
//        }
//        smallTail.next = largeHead.next;
//        largeTail.next = null;
//        return smallHead.next;
//    }
//}

//判断链表中存储的是不是回文
//空间复杂度为N(因为复制了一份),三步走,复制,逆转,比较,非常基础
//public class LinkedListProblem2 {
//    public boolean chkPalindrome(ListNode A){
//        //空链表和只有一个节点的链表,都视为回文
//        if(A == null){
//            return true;
//        }
//        if(A.next == null){
//            return true;
//        }
//        ListNode newHead = new ListNode(0);
//        ListNode newTail = newHead;
//        //复制链表
//        for(ListNode cur = A;cur != null;cur = cur.next){
//            ListNode newNode = new ListNode(cur.val);
//            newTail.next = newNode;
//            newTail = newNode;
//        }
//        //反转链表
//        ListNode prev = null;
//        ListNode cur = newHead;
//        while(cur != null){
//            ListNode next = cur.next;
//            if(next == null){
//                newHead = cur;
//            }
//            cur.next = prev;
//            prev = cur;
//            cur = next;
//        }
//        ListNode cur1 = A;
//        ListNode cur2 = newHead;
//        //开始比较
//        while(cur1 != null && cur2 != null){
//            if(cur1.val != cur2.val){
//                return false;
//            }
//            cur1 = cur1.next;
//            cur2 = cur2.next;
//        }
//        if(cur1.next == null&&cur2.next == null){
//            return true;
//        }
//        //说明两个链表长度不同,说明中间出错了
//        return false;
//    }
//}

//空间复杂度为1的写法,不创建新的链表,直接把原链表一分为二,后半部分进行逆转
//public class LinkedListProblem2{
//    public boolean chkPalindrome(ListNode A){
//        if(A == null){
//            return true;
//        }
//        if(A.next == null){
//            return false;
//        }
//        int mid = size(A) / 2;
//        ListNode B = A;
//        for(int i = 0;i < mid;i++){
//            B = B.next;
//        }
//        while(B != null){
//            B = B.next;
//        }
//        //这时B就变成了中间节点
//        ListNode prev = null;
//        ListNode cur = B;
//        while(B != null){
//            ListNode next = cur.next;
//            if(next == null){
//                B = cur;
//            }
//            cur.next = prev;
//            prev = cur;
//            cur = next;
//        }
//        //这时候B成了倒置后的头节点
//        //如果链表中元素个数为奇数的话,那么A,B表中元素个数相同,
//        //但是如果链表中元素个数为偶数的话,因为取得是靠后的元素,因此A表比B表多出一个元素
//        //比如链表长度是6,A的长度为4,B的长度为3,只需要把B比较完即可
//        while(A != null&&B != null){
//             if(A.val != B.val){
//                 return false;
//             }
//             A = A.next;
//             B = B.next;
//        }
//        return true;
//    }
//    public int size(ListNode head){
//        int size = 0;
//        for(ListNode cur = head;cur != null;cur = cur.next){
//            size++;
//        }
//        return size;
//    }
//}

//给定两个单链表的头节点,找出并返回两个单链表相交的起始节点,如果两个链表不存在相交节点,返回null
//思路:确定两个链表的长度,让长的链表走长度之差步,这样两个链表的长度就可以看作相等了,再让两个链表同时向后
//遍历,如果发现指向的位置相同,返回该位置,如果直到一个链表走完都没发现这个点,那就说明两个链表不相交,返回null
//public class LinkedListProblem2{
//    public ListNode getIntersectionNode(ListNode headA,ListNode headB){
//        int sizeA = size(headA);
//        int sizeB = size(headB);
//        int step = 0;
//        ListNode curA = headA;
//        ListNode curB = headB;
//        if(sizeA > sizeB){
//            step = sizeA - sizeB;
//            for(int i = 0;i < step;i++){
//                curA = curA.next;
//            }
//
//        }else{
//            step = sizeB - sizeA;
//            for(int i = 0;i < step;i++) {
//                curB = curB.next;
//            }
//        }
//        while(curA != null&&curB != null) {
//            curA = curA.next;
//            curB = curB.next;
//            if (curA == curB) {
//                return curB;
//            }
//        }
//        return null;
//    }
//    public int size(ListNode head){
//        int size = 0;
//        for(ListNode cur = head;cur != null;cur = cur.next){
//            size++;
//        }
//        return size;
//    }
//}

import java.util.ArrayList;
import java.util.List;

//给链表中的一个头节点,判断链表中是否有环
//public class LinkedListProblem2{
//    //最朴素的做法,使用顺序表存储链表中的每一个节点,接着遍历,如果有重复的,就说明链表中有环
//    //这样做的空间复杂度为O(N)
//    public boolean hasCycle(ListNode head){
//        //定义的顺序表存储ListNode类型的
//        List<ListNode> list = new ArrayList<>();
//        if(head == null){
//            return false;
//        }else{
//            for(ListNode cur = head;cur != null;cur = cur.next){
//                if(list.contains(cur)){
//                    return true
//                }else{
//                    list.add(cur);
//                }
//            }
//        }
//        return false;
//    }
//}

//牛逼解法(双指针法)
//思路:设定两个指针指向头节点,指针一个一次移动两步,一个一次移动一步,如果两个重合的话,说明链表是循环链表
//在Java叫做快慢引用
//如果快的移动3步,是不行的,假设有一个长度为2的循环,那么fast和slow会正好错开,一直不会相交,
// 举快的和慢的的差值的循环链表的反例即可理解这样不行,
//如果走两步的走到了头,说明链表不是循环链表(空间复杂度为0(1))
//public class LinkedListProblem2{
//    public boolean hasCycle(ListNode head){
//        if(head == null){
//            return false;
//        }
//        ListNode fast = head;
//        ListNode slow = head;
//        while(fast != null && fast.next != null){
//            fast = fast.next.next;
//            slow = slow.next;
//            if(slow == fast){
//                return true;
//            }
//        }
//        return false;
//    }
//}

//环形链表问题(要有好的数学思路),给定一个链表的头节点head,返回链表开始入环的第一个节点,如果链表无环,就返回null
//解题思路:同样使用双指针法,找到slow与fast交汇的位置,创建cur1从交汇位置出发,创建cur2从链表头部出发
//接着同时向后走,它们的交点就是入口点  cur1到入口点的距离是X,cur2到入口点的距离是L,当fast只是多循环了一圈时,
//L = X  数学推导:2*(L + R - X) = L + R + R - X  进而推出L = X;具体的图解可以看笔记
//当fast多循环了不止一圈时,这时候推导公式为:2*(L + R - X) = L + n * R + R - X
//这时候就是,L = X + (n - 1)*R,相当于L大于X,这时候仍然同时走,也是没有问题的,因为在vur2在L走的时候
// cur1会一直绕圈,直到两者相交,因此这种方法适用于所有情况
public class LinkedListProblem2{
    public ListNode dectectCycle(ListNode head){
        if(head == null){
            return null;
        }
        ListNode fast = head;
        ListNode slow = head;
        while(fast != null && fast.next!=null){
            slow = slow.next;
            fast = fast.next.next;
            if(slow == fast){
                break;
            }
        }
        if(fast == null && fast.next == null){
            return null;
        }
        ListNode cur1 = slow;
        ListNode cur2 = head;
        //通过数学已经推导出了cur1一定会与cur2相遇
        while(cur1 != cur2){
            cur1 = cur1.next;
            cur2 = cur2.next;
        }
        return cur1;
    }
}
